/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
#include <iostream>
#include <fstream>
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
  rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	if(pf.open(indexname, mode) == RC_FILE_OPEN_FAILED)
  {
    return RC_FILE_OPEN_FAILED;
  }
  if (pf.endPid() == 0)
  {
    return 0;
  }
  rootPid = 0;
  if (pf.endPid() == 1)
  {
    treeHeight = 0;
  }
  else 
  {
    BTNonLeafNode root;
    root.read(0, pf);
    treeHeight = root.getHeight();
  }
  return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid, int &curHeight, int &pid, int &newKey)
{				

	//inserting first root case
	if (rootPid == -1)
	{
		BTLeafNode root;
		root.insert(key, rid);
		root.setNextNodePtr(0);
		root.write(0, pf);
		rootPid = 0;
		return 0;
	}

	if (treeHeight == 0) //modifying initial root as leaf
	{
		BTLeafNode root;
		root.read(pid, pf);
		
		if (root.insert(key, rid)) //first root overflow
		{
			BTLeafNode newLeaf;
			newLeaf.setNextNodePtr(0);
			root.insertAndSplit(key, rid, newLeaf, newKey);
			root.setNextNodePtr(2);

			BTNonLeafNode newRoot;
			newRoot.initializeRoot(1, newKey, 2);
			newRoot.updateHeight(1);
			newRoot.write(0, pf);
			root.write(1, pf);
			newLeaf.write(2, pf);

			treeHeight = 1;
			return 0;
		}
		
		root.write(0, pf);
		
		return 0;
	}
	
	if (curHeight < treeHeight) //nonleaf node insertion (includes root case)
	{
		BTNonLeafNode cur;
		cur.read(pid, pf);
		int originalPid = pid;
		cur.locateChildPtr(key, pid);
		
		int nextHeight = curHeight + 1;
		
		if (insert(key, rid, nextHeight, pid, newKey)) //insertion caused leaf overflow
		{
			if (cur.insert(newKey, pid)) //
			{
				BTNonLeafNode newParent;
				cur.insertAndSplit(key, pid, newParent, newKey);
				
				if (curHeight == 0) //replaces root when root overflows
				{
					int newPid1 = pf.endPid();
          int newPid2 = pf.endPid() + 1;
				  
					BTNonLeafNode newRoot;
					newRoot.initializeRoot(newPid1, newKey, newPid2);

					treeHeight++;
					newRoot.updateHeight(treeHeight);

					newRoot.write(0, pf);
					cur.write(newPid1, pf);
					newParent.write(newPid2, pf);
					return 0;
				}
				
				pid = pf.endPid(); //overflow of non-root nonleafnode
				newParent.write(pid, pf);
				cur.write(originalPid, pf);
				return RC_NODE_FULL;
			}///##### shold there be code here?
		}
		
		cur.write(originalPid, pf); //always overwrite nonleaf node (root as of now)
	}
	else 
	{
		BTLeafNode leaf;
		leaf.read(pid, pf);
		if (leaf.insert(key, rid))
		{
			BTLeafNode newLeaf;
			newLeaf.setNextNodePtr(leaf.getNextNodePtr());
			leaf.insertAndSplit(key, rid, newLeaf, newKey);
			int originalPid = pid;
			pid = pf.endPid();
			leaf.setNextNodePtr(pid);

			newLeaf.write(pf.endPid(), pf);
			leaf.write(originalPid, pf);
			return RC_NODE_FULL;
		}
		leaf.write(pid, pf);
	}

    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor, int curHeight, int pid)
{
	if(curHeight == treeHeight) // leaf node/base case
	{
		BTLeafNode cur;
		cur.read(pid, pf);
		int eid;
		
		if(cur.locate(searchKey, eid))
		{
      cursor.pid = cur.getNextNodePtr();
      cursor.eid = 0;
      return 0;
		}
		else //set the cursor to our leaf properties
		{
			cursor.eid = eid;
			cursor.pid = pid;
			return 0;
		}
	}
	else if (curHeight < treeHeight) //non leaf node
	{
		BTNonLeafNode cur;
		cur.read(pid, pf);
		
		int nextpid; //page id of the next node
		
		if(cur.locateChildPtr(searchKey, nextpid))
		{
			return RC_NO_SUCH_RECORD;
		}
		else
		{ //follow the pointer
			if(locate(searchKey, cursor, curHeight + 1, nextpid))
			{
				return RC_NO_SUCH_RECORD;
			}
			else
			{
				return 0;
			}
		}
	}
	
    return RC_END_OF_TREE;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
  BTLeafNode cur;
  cur.read(cursor.pid, pf);
  cur.readEntry(cursor.eid, key, rid);
  if (cursor.eid < cur.getKeyCount() - 1)
  {
    cursor.eid++;
  }
  else
  {
    if (cur.getNextNodePtr() <= 0)
      return RC_END_OF_TREE;
    cursor.pid = cur.getNextNodePtr();
    cursor.eid = 0;
  }
  return 0;
}
